#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 岛屿的数量
class Solution
{
public:
    int m, n;
    bool vis[301][301];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int ret = 0;
    int numIslands(vector<vector<char>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    ret++;
                    dfs(grid, i, j);
                }
            }
        }

        return ret;
    }

    void dfs(vector<vector<char>> &grid, int i, int j)
    {
        grid[i][j] = true;

        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
            {
                dfs(grid, x, y);
            }
        }
    }
};

class Solution
{
public:
    int m, n;
    bool vis[301][301];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int ret = 0;
    int numIslands(vector<vector<char>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    ret++;
                    bfs(grid, i, j);
                }
            }
        }

        return ret;
    }

    void bfs(vector<vector<char>> &grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;

        while (q.size())
        {
            int a = q.front().first, b = q.front().second;
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
                {
                    vis[x][y] = true;
                    q.push({x, y});
                }
            }
        }
    }
};

// 腐烂的橘子
class Solution
{
public:
    int m, n;
    bool vis[11][11];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int orangesRotting(vector<vector<int>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        int freshCount = 0, ans = 0;
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    freshCount++;
                }
                else if (grid[i][j] == 2)
                {
                    q.push({i, j});
                }
            }
        }

        while (q.size())
        {
            int sz = q.size();
            // 记录这一次是否有腐烂的
            bool flags = false;
            for (int i = 0; i < sz; i++)
            {
                int a = q.front().first, b = q.front().second;
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
                    {
                        flags = true;
                        vis[x][y] = true;
                        q.push({x, y});
                        freshCount--;
                    }
                }
            }
            if (flags)
            {
                ans++;
            }
        }

        if (freshCount > 0)
            return -1;
        return ans;
    }
};

// 搜索插入位置
class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        // 插入位置为index,[left,index - 1] < target
        // [index,right] >= target
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }

        if (nums[right] < target)
            return right + 1;
        return right;
    }
};

// 搜索二维矩阵
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0)
        {
            if (matrix[i][j] == target)
            {
                return true;
            }
            else if (matrix[i][j] < target)
            {
                i++;
            }
            else
                j--;
        }

        return false;
    }
};
